public class MyQueue {
    //队列，从队尾插入数据，队头删除数据的一种数据结构
    //这里使用双向链表来实现队列
    //首先定义双线链表的节点
    public class ListNode {
        public int value;
        public ListNode prev;//前驱节点
        public ListNode next;//下一个节点
        //构造方法
        public ListNode(int value) {
            this.value = value;
        }
    }
    public ListNode head;//头节点
    public ListNode last;//末尾节点
    int size = 0;//元素个数
    //入队操作
    public void offer(int value) {
        //实例化一个节点，存放value
        ListNode node = new ListNode(value);
        //如果队列为空，放入的数据既是头节点，又是尾节点
        if(head == null) {
            head = last = node;
            size++;
        }else {
            //从队尾入队列
            last.next = node;
            node.prev = last;
            last = node;
            size++;
        }
    }
    //出队操作
    public int poll() {
        //队列为空直接返回-1
        if(head == null) {
            System.out.println("队列为空");
            return -1;
        }
        //队列不为空,只有一个节点的情况，出队列后将队列置为空
        int value;
        if(head.next == null) {
            value = head.value;
            head = null;
            last = null;
            size--;
            return value;
        }
        value = head.value;
        //head节点向后走
        head = head.next;
        //head的前驱节点置空
        head.prev = null;
        size--;
        return value;
    }
    //队列判空
    public boolean empty() {
        return head == null;
    }
    public int peek() {
        //拿到第一个出队列的元素
        if(head == null) {
            System.out.println("队列为空");
            return -1;
        }
        return head.value;
    }
    //拿到队列元素个数
    public int getSize() {
        return size;
    }
}
